package offer;

public class offerII_0026 {
    public void reorderList(ListNode head) {
        ListNode p=head;
        if(p.next==null||p.next.next==null) return;
        ListNode q=head.next;
        ListNode r=head.next.next;
        ListNode s=head;
        while(s.next.next!=null) s=s.next;
        while(r.next!=null){
            r=r.next;
        }
        while(true){
            p.next=r;
            r.next=q;
            s.next=null;

            if(q.next==s||q==s) break;
            s=head;
            p=q;
            q=q.next;
            while(s.next.next!=null) s=s.next;
            while(r.next!=null) r=r.next;
        }
        return;
    }
}
